package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 合并两个有序链表
 * @date 24/5/5 17:46
 */
public class Leetcode021 {

	/**
	 * 方法一：定义指针，遍历处理
	 * 1 3 8 9
	 * 2 4
	 *
	 * @param p1
	 * @param p2
	 * @return
	 */
	public static ListNode mergeTwoLists(ListNode p1, ListNode p2) {
		// 初始哨兵节点【此节点不能动，可以新增指针，指向这个，动指针即可】
		ListNode s = new ListNode(-1, null);
		ListNode p = s;
		while (p1 != null && p2 != null) {
			if (p1.val < p2.val) {
				p.next = p1;
				p1 = p1.next;
			}
			else {
				p.next = p2;
				p2 = p2.next;
			}
			p = p.next;
		}

		if (p1 != null) {
			p.next = p1;
		}
		else if (p2 != null) {
			p.next = p2;
		}

		return s.next;
	}

	/**
	 * 方法二：递归实现
	 *
	 * @param p1
	 * @param p2
	 * @return
	 */
	public static ListNode mergeTwoListsRecursion(ListNode p1, ListNode p2) {
		if (p1 == null) {
			return p2;
		}
		if (p2 == null) {
			return p1;
		}
		if (p1.val < p2.val) {
			p1.next = mergeTwoListsRecursion(p1.next, p2);
			return p1;
		}
		else {
			p2.next = mergeTwoListsRecursion(p1, p2.next);
			return p2;
		}
	}

	public static void main(String[] args) {
		ListNode p1 = ListNode.of(1, 3, 8, 9);
		ListNode p2 = ListNode.of(2, 4);
		// System.out.println(mergeTwoLists(p1, p2));
		System.out.println(mergeTwoListsRecursion(p1, p2));
	}

}
